Algoritmus: frekvencia fraz v subore
Otázka od: pointer
23. 5. 2004 8:52
Nazdar ,
mam textovy subor kde na kazdom riadku je nejaka fraza (1 az n slov) a
potrebujem spocitat kolkokrat sa kazda fraza v tom subore nachadza.
To som aj urobil ale ze vraj to pocita cca 30 MB subor viac ako 3 dni
;) a ze by to chcelo nejak urychlit..
Moj postup:
mam 2 stringlisty: InputLines a InputLinesUniq
V cykle nacitam zo suboru kazdy riadok a :
- cyklom skontrolujem ci uz rovnaka fraza nieje v InputLinesUniq
-ak nieje tak ju tam pridam
- pridam frazu do InputLines
takto po prejdeni celeho suboru mam v InputLines vsetky frazy presne
ako su v subore a v InputLinesUniq mam vsetky frazy iba raz.
A teraz prechadzam cyklom InputLinesUniq zoberiem aktualnu frazu a
a cyklom prejdem InputLines a pocitam kolkokrat sa tam nachadza:
for I := 0 to InputLinesUniq.Count - 1 do
begin
PhraseCount := 0;
for J := 0 to InputLines.Count - 1 do
IF (InputLinesUniq[I] = InputLines[J]) THEN INC(PhraseCount);
OutputLines.Add(IntToStr(PhraseCount) + ';' + InputLinesUniq[I]);
end;
OutputLines je StringList do ktoreho ukladam vysledok v tvare
"pocet_vyskytov;fraza"
Ide nejak jednoducho napisat lepsi (radovo rychlejsi) algoritmus ?
--
S pozdravom,
Michal Bilcik
Odpovedá: Pavol Stugel, NETGraphics
23. 5. 2004 9:11
co ja viem, tak napr.
1. nacitac cely subor naraz(vsetky frazi do zoznamu) (typu Fraza: String;
Count: Integer).
2. Quick sortom zoradis podla abecedy.
3. Jednoduchym cyklom ides frazu po fraze a pokial sa rovnaju tak vyhadzujes
frazy a pripocitavas k prvej (inc(count) 
da sa to aj efektivnejsie spravit kde by si mohol bod 2. vyhodit ale je to
komplikovanejsi algoritmus.
Napr. zmodifikujes Quick sort, aby ked sa rovnaju spravy tak iba pripocitaval
Count ...
Dalsia vec ze stringlist je pomerne pomaly na velkom zozname 
Palo
> Nazdar ,
>
> mam textovy subor kde na kazdom riadku je nejaka fraza (1 az n slov) a
> potrebujem spocitat kolkokrat sa kazda fraza v tom subore nachadza.
>
> To som aj urobil ale ze vraj to pocita cca 30 MB subor viac ako 3 dni
> ;) a ze by to chcelo nejak urychlit..
>
> Moj postup:
> mam 2 stringlisty: InputLines a InputLinesUniq
> V cykle nacitam zo suboru kazdy riadok a :
> - cyklom skontrolujem ci uz rovnaka fraza nieje v InputLinesUniq
> -ak nieje tak ju tam pridam
> - pridam frazu do InputLines
>
> takto po prejdeni celeho suboru mam v InputLines vsetky frazy presne
> ako su v subore a v InputLinesUniq mam vsetky frazy iba raz.
>
> A teraz prechadzam cyklom InputLinesUniq zoberiem aktualnu frazu a
> a cyklom prejdem InputLines a pocitam kolkokrat sa tam nachadza:
>
> for I := 0 to InputLinesUniq.Count - 1 do
> begin
> PhraseCount := 0;
> for J := 0 to InputLines.Count - 1 do
> IF (InputLinesUniq[I] = InputLines[J]) THEN INC(PhraseCount);
>
> OutputLines.Add(IntToStr(PhraseCount) + ';' + InputLinesUniq[I]);
> end;
>
> OutputLines je StringList do ktoreho ukladam vysledok v tvare
"pocet_vyskytov;fraza"
>
>
> Ide nejak jednoducho napisat lepsi (radovo rychlejsi) algoritmus ?
>
Odpovedá: Jiri Koula
23. 5. 2004 9:39
Hoj,
dalsi moznost je nacitat si ty fraze do stromu, kde z korene jdeme podle
prvniho pismene fraze do nektereho ze synu, obecne z i-te urovne do i+1-ve
urovne podle i+1-veho pismene fraze.
Po nacteni fraze ze souboru se ji snazis pridat do stromu, kdyz uz tam je,
zvysis pocet vyskytu (kazdy uzel se sklada z poctu + ukazatelu na
podstromy podle pismene), takhle to das v case (pocet zaznamu)*(prumerna
delka fraze) a pametove by to mohlo byt take unosne.
Pokud se ve frazich opakuji tataz slova v ruznych obmenach, mozna se
vyplati pohybovat se stromem po slovech, pointery na syny mohou byt take
dynamickou strukturou, pak uz to snad bude v pohode i pametove, nicmene v
kazdem pripade dosahnes IMHO nejrychlejsiho mozneho casu (aspon
asymptoticky, coz na tech Tvych 30 MB bude dobre meritko).
S pozdravem
Jiri Koula
On Sun, 23 May 2004, pointer wrote:
> Nazdar ,
>
> mam textovy subor kde na kazdom riadku je nejaka fraza (1 az n slov) a
> potrebujem spocitat kolkokrat sa kazda fraza v tom subore nachadza.
>
> To som aj urobil ale ze vraj to pocita cca 30 MB subor viac ako 3 dni
> ;) a ze by to chcelo nejak urychlit..
>
> Moj postup:
> mam 2 stringlisty: InputLines a InputLinesUniq
> V cykle nacitam zo suboru kazdy riadok a :
> - cyklom skontrolujem ci uz rovnaka fraza nieje v InputLinesUniq
> -ak nieje tak ju tam pridam
> - pridam frazu do InputLines
>
> takto po prejdeni celeho suboru mam v InputLines vsetky frazy presne
> ako su v subore a v InputLinesUniq mam vsetky frazy iba raz.
>
> A teraz prechadzam cyklom InputLinesUniq zoberiem aktualnu frazu a
> a cyklom prejdem InputLines a pocitam kolkokrat sa tam nachadza:
>
> for I := 0 to InputLinesUniq.Count - 1 do
> begin
> PhraseCount := 0;
> for J := 0 to InputLines.Count - 1 do
> IF (InputLinesUniq[I] = InputLines[J]) THEN INC(PhraseCount);
>
> OutputLines.Add(IntToStr(PhraseCount) + ';' + InputLinesUniq[I]);
> end;
>
> OutputLines je StringList do ktoreho ukladam vysledok v tvare
"pocet_vyskytov;fraza"
>
>
> Ide nejak jednoducho napisat lepsi (radovo rychlejsi) algoritmus ?
>
> --
> S pozdravom,
> Michal Bilcik
>
>
>
Odpovedá: pointer
24. 5. 2004 6:48
Nazdar ,
> Hoj,
> dalsi moznost je nacitat si ty fraze do stromu, kde z korene jdeme podle
> prvniho pismene fraze do nektereho ze synu, obecne z i-te urovne do i+1-ve
> urovne podle i+1-veho pismene fraze.
> Po nacteni fraze ze souboru se ji snazis pridat do stromu, kdyz uz tam je,
> zvysis pocet vyskytu (kazdy uzel se sklada z poctu + ukazatelu na
> podstromy podle pismene), takhle to das v case (pocet zaznamu)*(prumerna
> delka fraze) a pametove by to mohlo byt take unosne.
> Pokud se ve frazich opakuji tataz slova v ruznych obmenach, mozna se
> vyplati pohybovat se stromem po slovech, pointery na syny mohou byt take
> dynamickou strukturou, pak uz to snad bude v pohode i pametove, nicmene v
> kazdem pripade dosahnes IMHO nejrychlejsiho mozneho casu (aspon
> asymptoticky, coz na tech Tvych 30 MB bude dobre meritko).
> S pozdravem
> Jiri Koula
diky za namet, asi pojdem cestou vyhladavacieho stromu, do toho sa mi
najprv moc nechcelo ;)
Este ma napadlo: ma zmysel naprv substituovat vsetky frazy za nejake
cislo (rovnaka fraza = rovnake cislo) s tym predpokladom ze
porovnavanie cisiel je rychlejsie ako porovnavanie stringov ?
Ci nespotrebujem na vytvorenie tej prevodovej tabulky viac casu ako
potom usetrim...
> On Sun, 23 May 2004, pointer wrote:
>> Nazdar ,
>>
>> mam textovy subor kde na kazdom riadku je nejaka fraza (1 az n slov) a
>> potrebujem spocitat kolkokrat sa kazda fraza v tom subore nachadza.
>>
>> To som aj urobil ale ze vraj to pocita cca 30 MB subor viac ako 3 dni
>> ;) a ze by to chcelo nejak urychlit..
--
S pozdravom,
Michal Bilcik
Odpovedá: Jiri Koula
24. 5. 2004 9:58
Hoj,
> Este ma napadlo: ma zmysel naprv substituovat vsetky frazy za nejake
> cislo (rovnaka fraza = rovnake cislo) s tym predpokladom ze
> porovnavanie cisiel je rychlejsie ako porovnavanie stringov ?
> Ci nespotrebujem na vytvorenie tej prevodovej tabulky viac casu ako
> potom usetrim...
Prijde mi, ze aby to melo smysl, potreboval bys rychlou hashovaci funkci,
u niz bys mel zarucenou bezkoliznost, protoze kdyby Ti pro dve fraze
vratila stejne cislo, asi by to byl prusvih... A navic pri vypoctu teto
funkce bys stejne musel kazdy string znak po znaku projit, ne? IMHO tim
prevodem spotrebujes vic casu, nebot bez prevodu pro kazdy znak udelas
operaci porovnani znaku, pri prevodu s hodnotou toho znaku budes jeste
muset nejak operovat, aby prispela k celkovemu cislu.
S pozdravem
Jiri Koula
Odpovedá: Daniel Frantik
25. 5. 2004 14:15
> diky za namet, asi pojdem cestou vyhladavacieho stromu, do
> toho sa mi najprv moc nechcelo ;) Este ma napadlo: ma zmysel
> naprv substituovat vsetky frazy za nejake cislo (rovnaka
> fraza = rovnake cislo) s tym predpokladom ze porovnavanie
> cisiel je rychlejsie ako porovnavanie stringov ? Ci
> nespotrebujem na vytvorenie tej prevodovej tabulky viac casu
> ako potom usetrim...
Tohle je jako delana na hashovani. Ze slozitosti n*n se dostanes na
n*log(n) coz je na 30M znat. Svoji roli taky asi hraji soustavne
realokace stringu (podivej se jak ti to zatezuje jadro). Kdosi tady
navrhoval ze musis mit hashovaci funkci ktera ti vzdy vrati unikatni
hash.... to samozrejme nemusis, jem musis nejak rozume resit kolize kdy
ti vyjde stejny hash pro vice slov... Hasovani by mohlo mit lepsi
uspesnost nez strom, protoze ve vetsine pripadu by ti mohl stacit prvni
pokus...
Danik
Odpovedá: Daniel Frantik
25. 5. 2004 14:08
> -----Original Message-----
> Hoj,
> Prijde mi, ze aby to melo smysl, potreboval bys rychlou
> hashovaci funkci, u niz bys mel zarucenou bezkoliznost,
> protoze kdyby Ti pro dve fraze vratila stejne cislo, asi by
> to byl prusvih... A navic pri vypoctu teto funkce bys stejne
> musel kazdy string znak po znaku projit, ne? IMHO tim
> prevodem spotrebujes vic casu, nebot bez prevodu pro kazdy
> znak udelas operaci porovnani znaku, pri prevodu s hodnotou
> toho znaku budes jeste muset nejak operovat, aby prispela k
> celkovemu cislu. S pozdravem
Problem neni v prochazeni slova ale v prochazeni celeho seznamu jiz
znamych slov pro kazde pridavane slovo ... (n*n) Takze hasovani
doporucuji. (bezkoliznost je termin co nema u hasovani prilis smysl
...).
Co se tyce reseni pres stromy tak v podstate staci setrideny stringlist
a binarni prohledavani.
Danik
Odpovedá: delphin@post.cz
25. 5. 2004 14:31
> > Hoj,
> > Prijde mi, ze aby to melo smysl, potreboval bys rychlou
> > hashovaci funkci, u niz bys mel zarucenou bezkoliznost,
> > protoze kdyby Ti pro dve fraze vratila stejne cislo, asi by
> > to byl prusvih... A navic pri vypoctu teto funkce bys stejne
> > musel kazdy string znak po znaku projit, ne? IMHO tim
> > prevodem spotrebujes vic casu, nebot bez prevodu pro kazdy
> > znak udelas operaci porovnani znaku, pri prevodu s hodnotou
> > toho znaku budes jeste muset nejak operovat, aby prispela k
> > celkovemu cislu. S pozdravem
> Problem neni v prochazeni slova ale v prochazeni celeho seznamu jiz
> znamych slov pro kazde pridavane slovo ... (n*n) Takze hasovani
> doporucuji. (bezkoliznost je termin co nema u hasovani prilis smysl
> ...).
> Co se tyce reseni pres stromy tak v podstate staci setrideny stringlist
> a binarni prohledavani.
Jeste je moznost eliminovat opakovane prohledavani stromu:
1) Udelat hash pro kazdy string
2) Setridit hashe quick sortem
3) Projit v cyklu setridene hashe. Stejne hodnoty budou za sebou.
Odpovedá: Daniel Frantik
25. 5. 2004 14:48
> -----Original Message-----
> Jeste je moznost eliminovat opakovane prohledavani stromu:
> 1) Udelat hash pro kazdy string
> 2) Setridit hashe quick sortem
> 3) Projit v cyklu setridene hashe. Stejne hodnoty budou za sebou.
Kdyz u hashe tak jimi primo indexovat pole ... Bud strom (popr. trideny
stringlist) nebo (lepe) hashem primo indexovat pole, kde v bunce muze
byt 1-n slov... (optimalne jedno 
Danik
Odpovedá: Jiri Koula
25. 5. 2004 17:50
> Problem neni v prochazeni slova ale v prochazeni celeho seznamu jiz
> znamych slov pro kazde pridavane slovo ... (n*n) Takze hasovani
> doporucuji. (bezkoliznost je termin co nema u hasovani prilis smysl
> ...).
> Co se tyce reseni pres stromy tak v podstate staci setrideny stringlist
> a binarni prohledavani.
Dovolim si oponovat, v pripade, ze jsem mimo, se aspon neco priucim a
napravim spatne spoje v mozku. Totiz nevidim duvod, proc bych porovnaval
kazde slovo (coz je predpokladam ekvivalent k terminu fraze) se vsemi
novymi - mam stom, ktery po slovech "ahoj" "aha" "ale" vypada
a-h-o-j
-a
-l-e
(snad je jasne, jak vypada), kdyz mi prijde nove slovo, podivam se na
prvni znak, podle toho jdu do urcite vetve, pak na druhy znak, ... az se
dostanu na konec do nejakeho uzlu, ktery kdyz existuje, zvysim v nem
pocet vyskytu, kdyz neexistuje, mam vyskyt jedna.
Takto pro kazde slovo provedu x porovnani, kde x je pocet znaku slova,
takze provedu radove n*x operaci, kde x je prumerna delka slova - dovolim
si predpokladat, ze x bude na 30 MB mensi nez log n.
Tak kde je tech n^2 a prochazeni vsech predchozich slov, jez zminujes?
S pozdravem
Jiri Koula
Odpovedá: Jiri Koula
25. 5. 2004 18:10
> Tohle je jako delana na hashovani. Ze slozitosti n*n se dostanes na
> n*log(n) coz je na 30M znat. Svoji roli taky asi hraji soustavne
> realokace stringu (podivej se jak ti to zatezuje jadro). Kdosi tady
> navrhoval ze musis mit hashovaci funkci ktera ti vzdy vrati unikatni
> hash.... to samozrejme nemusis, jem musis nejak rozume resit kolize kdy
> ti vyjde stejny hash pro vice slov... Hasovani by mohlo mit lepsi
> uspesnost nez strom, protoze ve vetsine pripadu by ti mohl stacit prvni
> pokus...
Ad minuly prispevek, ja se dostanu asymptoticky na linearni slozitost,
otazkou je, jak bude mit velkou konstantu v porovnani s log n.
Co se tyce kolizi, pokud jsem pochopil puvodni myslenku, chtel si autor
nejdrive vsechny fraze prevest hashovaci fci na cisla a s tema pak
pracovat. Ovsem pri vznikle kolizi (tim myslim, ze hashovaci funkce neni
prosta - zobrazi dve fraze na stejne cislo) mame problem a musime ho resit
za pouziti znalosti puvodnich frazi a jsme zase u porovnavani stringu a
slozitosti n*n.
Pokud chapu Tvuj navrh, tak vezmes string, zhashujes ho a podivas se do
tabulky, zda to je ten samy string, pokud ne, divas se nekam vedle,
pripadne mas u kazdeho zaznamu spojak (to je asi standardni postup). Ovsem
to musis nejdrive provest onu funkci a pak ten string stejne znak po znaku
zkontrolovat. Ja ve svem reseni jenom kontroluji znak po znaku a vzdy se
zarucene trefim na prvni pokus.
Zbyva tedy otazka, zda je vypocet one hashovaci funkce rychlejsi nez moje
pointerova aritmetika pri pruchodu stromem, coz uznavam by pri rozumnych
frazich a hashovaci funkci byt mohlo, nebot pro vypocet one funkce neni
asi treba brat cely string.
BTW, nejak nevidim v Tvem navrhu onu slozitost n*log n, totiz na co
potrebujes ten logaritmus - pro pruchod te hashovaci tabulky pri kolizi?
Pokud by sis u kazdeho zaznamu udelal neco jako vyhladavaci strom, projdes
ji v case x, kde x je delka fraze, celkovy pocet zaznamu Te trapit
nemusi...
Ovsem to uz jsme u kompromisniho reseni hashovat a v pripade potreby
nasadit muj postup, to by mohlo byt nejrychlejsi (pri rozumne hashovaci
funkci by se odliseni koliznich stringu dalo vychytat po par znacich)
...
Shnuto - uznavam, hashovani je dobra volba, ovsem asymptoticky jsme na tom
stejne ...
S pozdravem
Jiri Koula
>
> Danik
>
>
>
>
Odpovedá: Daniel Frantik
25. 5. 2004 18:30
> -----Original Message-----
> Totiz nevidim duvod,
> proc bych porovnaval kazde slovo (coz je predpokladam
> ekvivalent k terminu fraze) se vsemi novymi - mam stom, ktery
> po slovech "ahoj" "aha" "ale" vypada
>
> a-h-o-j
> -a
> -l-e
Pochopil jsem to tak, ze do stromu budes do uzlu cpat cela slova - to
tve je samozrejme lepsi
Nicmene: ten strom musi
a) bud reprezentovat v kazdem uzlu polem pro kazdy znak -> zbesile
narusta pametova narocnost
b) nejaky seznam pouzitych pismen a odkazu na dalsi uzel z nic -> tam
to zase neni uplne linearni slozitost najit to pismeno a to bude troufam
si tvrdit slozitejsi nez porovnat dva kratke retezce
>
> Takto pro kazde slovo provedu x porovnani, kde x je pocet
> znaku slova, takze provedu radove n*x operaci, kde x je
> prumerna delka slova - dovolim si predpokladat, ze x bude na
> 30 MB mensi nez log n.
Souhlas az na predeslou pripominku... (*y kde y je prumerny pocet
deti urciteho uzlu)
> Tak kde je tech n^2 a prochazeni vsech predchozich slov, jez zminujes?
n*n je slozitost puvodniho (nestromoveho) reseni... pokud jsem o
stromech napsal toto, tak sorry
>nejak nevidim v Tvem navrhu onu slozitost n*log n
mas pravdu - myslel jsem tim hledani po kolizi ale asi to bude spis 1
nez log(n) - moje chyba
>Shnuto - uznavam, hashovani je dobra volba, ovsem asymptoticky jsme na
tom stejne ...
Ja si nemyslim ze stromy by na tom byly nejak spatne, ale implementacne
mi pripada jednodussi udelat si tabulku rekneme o 4096 polozkach, hashem
do ni ziskat index a na kazde bunce tabulky si drzet seznam (stringlist)
sem zahashovanych slov. Vzhledem k bezne slovni zasobe cca 30.000 slov
bych cekal tak 1-2 slova na kazdou bunku coz je dost v pohode a nedrel
bych se se stromem Nicmene pokud by slovy byla opravdu hooodne
ruzna, hashovani bude mit problem a stromy jsou lepsi volba ...
Danik
Odpovedá: Jiri Koula
25. 5. 2004 19:30
Hoj,
> Nicmene: ten strom musi
> a) bud reprezentovat v kazdem uzlu polem pro kazdy znak -> zbesile
> narusta pametova narocnost
Souhlasim, nicmene v puvodnim reseni autor nacpal do pameti tech 30 MB a
jeste jednou neco srovnatelne velkeho - takze ho pamet asi netrapi ...
> b) nejaky seznam pouzitych pismen a odkazu na dalsi uzel z nic -> tam
> to zase neni uplne linearni slozitost najit to pismeno a to bude troufam
> si tvrdit slozitejsi nez porovnat dva kratke retezce
No, muzu mit seznam pouzitych pismen (kterych je rekneme 50) v binarnim
stromu (vysky 5) a projit si pet urovni zas tak narocne nebude
> Ja si nemyslim ze stromy by na tom byly nejak spatne, ale implementacne
> mi pripada jednodussi udelat si tabulku rekneme o 4096 polozkach, hashem
> do ni ziskat index a na kazde bunce tabulky si drzet seznam (stringlist)
> sem zahashovanych slov. Vzhledem k bezne slovni zasobe cca 30.000 slov
> bych cekal tak 1-2 slova na kazdou bunku coz je dost v pohode a nedrel
> bych se se stromem Nicmene pokud by slovy byla opravdu hooodne
> ruzna, hashovani bude mit problem a stromy jsou lepsi volba ...
Priznavam, ze kdybych si mel vybrat mezi implementaci Tveho a meho
navrhu, vybral bych si Tvuj, bo bych to dal radove 10x rychleji - a o tom
to taky hodne je ... No, doufam, ze tato prestrelka autorovi puvodniho
problemu aspon neco dala ...
S pozdravem
Jiri Koula
Odpovedá: Daniel Frantik
26. 5. 2004 9:03
> -----Original Message-----
> > Nicmene: ten strom musi
> > a) bud reprezentovat v kazdem uzlu polem pro kazdy znak
> -> zbesile
> > narusta pametova narocnost
> Souhlasim, nicmene v puvodnim reseni autor nacpal do pameti
> tech 30 MB a jeste jednou neco srovnatelne velkeho - takze ho
> pamet asi netrapi ...
Pokud akceptujes 50 ruznych pismen musis mit v kazdem uzlu 50 bytove
pole -> pri hloubce stromu 5 je pamet cca 50^5=300MB ... a pri vetsi
hloubce uz koncis ... - nejesna se totiz o binarni strom - oprav me
pokud se pletu . Takze tohle je podle me nepouzitelna reprezentace
(musis pouzit b)
> No, muzu mit seznam pouzitych pismen (kterych je rekneme 50)
> v binarnim stromu (vysky 5) a projit si pet urovni zas tak
> narocne nebude
prave ze to nebude binarni strom - aspon jak tvuj navrh chapu. Jen tak
pro pokus zarad do sveho stromu slova "bagr" a "cukr" - uz potrebujes z
rootu mit 3 vazby dolu -> neni to binarni... -> vy\zdy v kazdem uzlu
musis projit seznam pismen v nem uchovavanych a pokud je to 50, bude to
pomalejsi nez retezcove porovnani
> rychleji - a o tom to taky hodne je ... No, doufam, ze tato
> prestrelka autorovi puvodniho problemu aspon neco dala ...
Snad jo
Hezky den,
Danik
Odpovedá: Bohuslav Svancara
26. 5. 2004 10:07
Nezkousel jsi pro zajimavost dat to do databaze, udelat index a jak dlouho
by trval select?
select fraze, count(fraze) from tabulka group by fraze
S pozdravem
Bohuslav Svancara, prom. mat.
svancara@softprojekt.cz
> -----Original Message-----
> From: delphi-l-owner@clexpert.cz
> [mailto:delphi-l-owner@clexpert.cz]On Behalf Of pointer
> Sent: Sunday, May 23, 2004 9:33 AM
> To: delphi-l@clexpert.cz
> Subject: Algoritmus: frekvencia fraz v subore
>
>
> Nazdar ,
>
> mam textovy subor kde na kazdom riadku je nejaka fraza (1 az n slov) a
> potrebujem spocitat kolkokrat sa kazda fraza v tom subore nachadza.
>
> To som aj urobil ale ze vraj to pocita cca 30 MB subor viac ako 3 dni
> ;) a ze by to chcelo nejak urychlit..
>
> Moj postup:
> mam 2 stringlisty: InputLines a InputLinesUniq
> V cykle nacitam zo suboru kazdy riadok a :
> - cyklom skontrolujem ci uz rovnaka fraza nieje v InputLinesUniq
> -ak nieje tak ju tam pridam
> - pridam frazu do InputLines
>
> takto po prejdeni celeho suboru mam v InputLines vsetky frazy presne
> ako su v subore a v InputLinesUniq mam vsetky frazy iba raz.
>
> A teraz prechadzam cyklom InputLinesUniq zoberiem aktualnu frazu a
> a cyklom prejdem InputLines a pocitam kolkokrat sa tam nachadza:
>
> for I := 0 to InputLinesUniq.Count - 1 do
> begin
> PhraseCount := 0;
> for J := 0 to InputLines.Count - 1 do
> IF (InputLinesUniq[I] = InputLines[J]) THEN INC(PhraseCount);
>
> OutputLines.Add(IntToStr(PhraseCount) + ';' + InputLinesUniq[I]);
> end;
>
> OutputLines je StringList do ktoreho ukladam vysledok v tvare
> "pocet_vyskytov;fraza"
>
>
> Ide nejak jednoducho napisat lepsi (radovo rychlejsi) algoritmus ?
>
> --
> S pozdravom,
> Michal Bilcik
>
>
>
>
Odpovedá: Jiri Cincura
26. 5. 2004 14:23
Ldyz uz tady nekdo zminil tries, jejich popis (a jeste plno kecu k B/B+...
stromum) najdete tady:
http://www.fi.muni.cz/usr/staudek/vyuka/filesys/09_B_stromy.pdf
--
Jiri Cincura
e-mail: mailto:jiri@cincura.net; mailto:xcincura@informatics.muni.cz
ICQ: 314711544
web: http://www.cincura.net; http://cincura.net/photo